#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class MinPrice:
    RAW_VALUE = -1

    def __init__(self):
        self.house_price = [
            [100, 77, 73],
            [41, 74, 83],
            [9, 91, 93],
            [50, 16, 31],
        ]

        self.next_color = [
            (1, 2),
            (0, 2),
            (0, 1)
        ]

        self.n = len(self.house_price)

        self.init_memory()

    def init_memory(self):
        one_line = 3 * [self.RAW_VALUE]

        # HINT: self.memory : 一个 (n+1) * 3的 矩阵/二维数组, 用来查表, 空间换时间
        self.memory = [list(one_line) for i in range(self.n+1)]

        # HINT: 初始化递归边界
        for color_idx in range(3):
            self.memory[self.n][color_idx] = 0

    def min_house(self):
        # 从第0所房子开始
        return min(self.min_house_rec(0, 0), self.min_house_rec(0, 1), self.min_house_rec(0, 2))

    def min_house_rec(self, from_house_kth, color_kth):
        # 从from_house_kth 到 第n座房子的最低价格

        price = self.memory[from_house_kth][color_kth]

        if price != self.RAW_VALUE:
            return price

        cur_price = self.house_price[from_house_kth][color_kth]

        color1 = self.next_color[color_kth][0]
        color2 = self.next_color[color_kth][1]
        follows_min = min(self.min_house_rec(from_house_kth+1, color1), self.min_house_rec(from_house_kth+1, color2))

        price = cur_price + follows_min
        self.memory[from_house_kth][color_kth] = price

        return price

def test():
    m = MinPrice()
    p = m.min_house()
    print(p)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
